Gradient Descent from MATH102#
import numpy as np
from scipy.integrate import solve_ivp
try:
import plotly.graph_objects as go
except:
!pip install plotly
import plotly.graph_objects as go
Theory#
Oppgave 4. La \(f \colon \mathbb{R}^2 \to \mathbb{R}\) være deriverbar og la \(\mathbf{y}\colon \mathbb{R}\to \mathbb{R}^2\) være en deriverbar kurve slik at \(\mathbf{y}'(t) = -\nabla f(\mathbf{y}(t))\). Forklar hvorfor funksjonen \(f(\mathbf{y}(t))\) ikke er voksende rundt noen \(t \in \mathbb{R}\).
Strategi: Hvis \(\mathbf{y}\) er som i oppgaven ovenfor, og nærmer \(\mathbf{y}(t)\) seg et punkt \(\mathbf{x}_0\) når \(t\) blir stor så er kanskje dette punktet et lokalt minimumspunkt for \(f\). Mange steder brukes dette til å søke etter lokale minimumspunkter for \(f\). Hvis vi klarer å finne et slik punkt \(\mathbf{x}_0\) kan vi bruke andrederiverttesten til å prøve å vise at det er et lokalt minimumspunkt.
Hvis vi er gitt et startpunkt \(\mathbf{y}_0\) kan vi prøve å finne en løsning til differensialligningen \(\mathbf{y}'(t) = -\nabla f(\mathbf{y}(t))\) med startbetingelse \(\mathbf{y}(0) = \mathbf{y}_0\) og se hvilket punkt \(\mathbf{y}(t)\) går mot når \(t\) blir stor.
Lemma La \(f \colon \mathbb{R}^n \to \mathbb{R}\) være kontinuerlig deriverbar. Hvis \(\mathbf{y}(t)\) er en løsning til differensialligningen \(\mathbf{y}'(t) = -\nabla f(\mathbf{y}(t))\) og \(\lim_{t \to \infty} \mathbf{y}(t) = \mathbf{p}\) for en \(\mathbf{p} \in \mathbb{R}^n\), da er \(\nabla f(\mathbf{p}) = 0\)
Konsekvens: Siden \(f \circ \mathbf{y}\) ikke er voksende er \(\mathbf{p} = \lim_{t \to \infty} \mathbf{y}(t)\) enten et lokalt minimum eller et saddelpunkt, det vil si, et kritisk punkt for \(f\) som verken er et lokalt minimum eller et lokalt maksimum.
Forklaring: At \(f\) er kontinuerlig deriverbar betyr at funksjonen \(\mathbf{x} \mapsto \nabla f(\mathbf{x})\) er kontinuerlig.
Siden denne funksjonen er kontinuerlig og \(\lim_{t \to \infty} \mathbf{y}(t) = \mathbf{p}\) vet vi at
Derfor er $\(\lim_{t \to \infty} (f \circ \mathbf{y})'(t) = \lim_{t\to \infty} \nabla f'(\mathbf{y}(t)) \cdot \mathbf{y}'(t) = \lim_{t\to \infty} -|\nabla f(\mathbf{y}(t))|^2 = -|\nabla f(\mathbf{p})|^2.\)$
Siden er \(f\) og \(\mathbf{y}\) er deriverbare er de også kontinuerlige.
Derfor er også \((f \circ \mathbf{y})\) kontinuerlig slik at \((f \circ \mathbf{y})(t) \to f (\mathbf{p})\) for \(t \to \infty\).
Derfor kan ikke \(\lim_{t \to \infty} (f \circ \mathbf{y})'(t)\) konvergere til et tall forskjellig fra null, slik at \(\nabla f(\mathbf{p}) = 0\) er eneste mulighet.
Eksempel#
\(f(x) = e^{-x_1^2 - x_2^2}\)
# @title Plotter
def f(x):
x1, x2 = x
# bemerk at hvis x ikke er i D, da lar vi f være ikke definert, eller nan for not a number
return -np.exp(-x1**2 - x2**2)
def gradientf(x1, x2):
return np.array(2*x1*np.exp(-x1**2 - x2**2), 2*x2*np.exp(-x1**2 - x2**2))
def dy(t, y):
return -gradientf(y[0], y[1])
sol = solve_ivp(dy, t_span=[0, 100], y0=[0.5, 0.5], t_eval=np.linspace(0, 100, 1000))
# Create a grid of x and y values
x1 = np.linspace(-1, 1, 300)
x2 = np.linspace(-1, 1, 300)
#x1 = np.sign(x1) * np.sqrt(np.abs(x1))
#x2 = np.sign(x2) * np.sqrt(np.abs(x2))
x = np.meshgrid(x1, x2)
# Compute the function values
x3 = f(x)
# Create figure
fig = go.Figure()
# Add surface
fig.add_surface(
x=x[0], y=x[1], z=x3, colorscale="Viridis", opacity=0.8
)
# Add curve
fig.add_scatter3d(
x=sol.y[0], y=sol.y[1], z=f(sol.y), mode="lines", line=dict(color="red", width=10)
)
fig.show()